package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.List;

public class Code12_NQueens {

	public static void putDownTheQueen(int x, int y, int[][] mark) {
		int[] dx = new int[] { -1, 1, 0, 0, -1, -1, 1, 1 };
		int[] dy = new int[] { 0, 0, -1, 1, -1, 1, -1, 1 };

		mark[x][y] = 1;
		int n = mark.length;
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < 8; j++) {
				int newX = x + i * dx[j];
				int newY = y + i * dy[j];
				if (newX < n && newX >= 0 && newY < n && newY >= 0) {
					mark[newX][newY] = 1;
				}
			}
		}
	}

	static int ways = 0;

	public static void generate(int row, int n, char[][] location, List<List<String>> result, int[][] mark) {
		if (row == n) {
			ways++;
			result.add(construct(location));
			return;
		}

		for (int col = 0; col < n; col++) {
			if (mark[row][col] == 0) {
				int[][] tmp_mark = new int[n][n];
//				tmp_mark = mark;
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						tmp_mark[i][j] = mark[i][j];
					}
				}

				location[row][col] = 'Q';
				putDownTheQueen(row, col, mark);
				generate(row + 1, n, location, result, mark);
				mark = tmp_mark;
				location[row][col] = '.';
			}
		}
	}

	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// 把数组转为list
	private static List<String> construct(char[][] chess) {
		List<String> path = new ArrayList<String>();
		for (int i = 0; i < chess.length; i++) {
			path.add(new String(chess[i]));
		}

		return path;
	}

	public static List<List<String>> solveNQueens(int n, List<List<String>> result) {
		int[][] mark = new int[n][n];
		char[][] location = new char[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				mark[i][j] = 0;
				location[i][j] = '.';
			}
		}

		generate(0, n, location, result, mark);
		return result;
	}

	public static void main(String[] args) {
		List<List<String>> result = new ArrayList<>();
		result = solveNQueens(8, result);
		System.out.println(ways);
		System.out.println(result);
	}

//	输入：4
//	输出：[
//	 [".Q..",  // 解法 1
//	  "...Q",
//	  "Q...",
//	  "..Q."],
//
//	 ["..Q.",  // 解法 2
//	  "Q...",
//	  "...Q",
//	  ".Q.."]
//	]
//	解释: 4 皇后问题存在两个不同的解法。
}
